package LeetCode;

import java.util.Stack;

public class Code84_largestRectangleArea {
    // 维护一个递增站，每弹一个出来，计算以弹出元素为高度的最大面积
    public int largestRectangleArea(int[] heights) {
        if (heights == null || heights.length == 0){
            return 0;
        }
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < heights.length; i++) {
            while (stack.peek() != -1 && heights[stack.peek()] > heights[i]){
                max = Math.max(max, heights[stack.pop()] * (i - stack.peek() - 1));
            }
            stack.push(i);
        }
        while (stack.peek() != -1){
            max = Math.max(max, heights[stack.pop()] * (heights.length - stack.peek() - 1));
        }
        return max;
    }

    public static void main(String[] args) {
        Code84_largestRectangleArea code84_largestRectangleArea = new Code84_largestRectangleArea();
        int[] heights = new int[]{5,4,1,2};
        System.out.println(code84_largestRectangleArea.largestRectangleArea(heights));
    }
}
